Міністерство освіти та науки України Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій Кафедра ІСМ Лабораторна робота № 7 з дисципліни : " Комп’ютерні мережі" на тему: “ Код Хемінга ” Мета роботи: вивчення будови одного з найпростіших систематичних кодів - коду Хемінга, та дослідження його коректуючих властивостей. ТЕОРЕТИЧНІ ВІДОМОСТІ. В процесі автоматизованого управління технікою, виробничими процесами, галузями народного господарства, а також в процесах творчої діяльності людини відбувається інтенсивний обмін інформацією між окремими ланками систем управління, між людиною та технікою, людиною та природою, між окремими людьми. Bci ці процеси пов’язані з отриманням, передачею, перетворенням, накопиченням збереженням та відображенням інформації. Структурна схема інформаційної системи наведена на рис.1. Рис.1. Структурна схема інформаційної системи. Повідомлення, для передачі його по відповідній адресі повинно бути спочатку перетворено у сигнал. Під кодуванням в широкому розумні цього слова розуміють процес перетворення повідомлень у сигнал. Завадостійкі коди - один з найбільш ефективних зacoбiв забезпечення високої достовірності передачі дискретної інформації. Завадостійкі коди - це коди, які дозволяють викривати та виправляти помилки, які виникають через дію завад. Завадостійкість кодування забезпечується за рахунок введення надлишковості в код; комбінації, тобто за рахунок того, що символи в кодових комбінаціях використовуються для передачі інформації повідомлення. Одним з параметрів, що характеризує ступінь надлишковості коду є кодова відстань. Кодова відстань - це мінімальна кількість одиниць в сумі двох довільних кодових комбінацій коду. Кодова відстань, таким чином описує мінімальну розбіжність двох кодових комбінацій. Bci завадостійкі коди можна поділити на два основних класи: блочні та неперервні. В блочних кодах кожному повідомленню (або його елементу) ставиться у відповідність кодова комбінація (блок) з певної кількості символів. Блоки кодуються та декодуються незалежно один від другого. На сьогоднішній день найбільш широкий клас коректуючих кодів складають систематичні коди. Ці коди відносяться до груп блочних кодів. Для систематичного коду сума по модулю два, двох дозволених кодових комбінацій також дає дозволену кодову комбінацію. Одним з систематичних кодів є код Хемінга. Відомо кілька різновидів коду Хемінга, які характеризуються різними коректуючими властивостями. До цих кодів звичайно відносять коди з виправленням однократних помилок та виявленням двохкратних помилок. Код Хемінга, який забезпечує виправлення вcix однократних помилок мусить мати мінімальну кодову відстань: D min=3 Довжина ходу n вибирається виходячи з такої умови: 2^k<=2^n/(1+n) де k - кількість інформаційних символів. Код будується таким чином, щоб в результаті r = п * k отримати r - розрядне двійкове число, яке вказує на номер спотвореного символу в кодовій комбінації. Для цього перевірочні символи повинні знаходитися в номерах позицій, що виражаються ступенем двійки так як кожний з них входить в одно перевірочне рівняння. Таким чином, якщо нумерувати позиції зліва направо, то контрольні символи повинні знаходитися, в першій, другій, четверті позиціях. Наприклад, розташування символів в коді Хемінга з п = 9 буде таким: а(1) а(2) а(3) а(4) а(5) а(6) а(7) а(8) а(9) r(1) r(2) k(1) r(3) k(2) k(3) k(4) r(4) k(5) Результат першої перевірки дає цифру молодшого розряду синдрому в двійковому записі. Якщо результат такої перевірки 1, то один з символів групи, що перевіряється спотворено. Таким, чином, першою перевіркою повинні бути охоплені символи з номерами, які мають в двійковому запису одиниці в першому розряді: 1, 3, 5, 7, 9 i т. д. Результат другої перевірки дає цифру другого розряду синдрому. Тому, другою перевіркою треба охопити символи з номерами, як( містять в двійковій формі запису одиницю в другому розряді : 2, 3, 6...